\subsection{Transportation tableaux}
Analogously to the simplex tableaux, for the transport problem we can create transportation tableaux.
This is a convenient format for storing all relevant information for the transport problem while solving it.
The transportation tableau is as follows:

\[
	\arraycolsep=2pt\def\arraystretch{1.2}
	\begin{array}{c|c|c|c|c|c|c|c|c|c}
		\multicolumn{1}{c}{}           & \multicolumn{2}{c}{\mu_1}                        & \multicolumn{2}{c}{\mu_2}                        & \multicolumn{2}{c}{\cdots}                       & \multicolumn{2}{c}{\mu_m}                        & \multicolumn{1}{c}{}                                                         \\\cline{2-9}
		\multirow{2}{*}{\(\lambda_1\)} & \multicolumn{2}{c|}{\lambda_1 + \mu_1}           & \multicolumn{2}{c|}{\lambda_1 + \mu_2}           & \multicolumn{2}{c|}{\multirow{2}{*}{\(\cdots\)}} & \multicolumn{2}{c|}{\lambda_1 + \mu_m}           & \multirow{2}{*}{\(s_1\)}                                                     \\\cline{3-3}\cline{5-5}\cline{9-9}
		                               & \multicolumn{1}{c|}{x_{11}}                      & c_{11}                                           & \multicolumn{1}{c|}{x_{12}}                      & c_{12}                                           & \multicolumn{2}{c|}{\ \;\qquad\;\ } & \multicolumn{1}{c|}{x_{1m}} & c_{1m} & \\\cline{2-9}
		\multirow{2}{*}{\(\lambda_2\)} & \multicolumn{2}{c|}{\lambda_2 + \mu_1}           & \multicolumn{2}{c|}{\lambda_2 + \mu_2}           & \multicolumn{2}{c|}{\multirow{2}{*}{\(\cdots\)}} & \multicolumn{2}{c|}{\lambda_2 + \mu_m}           & \multirow{2}{*}{\(s_2\)}                                                     \\\cline{3-3}\cline{5-5}\cline{9-9}
		                               & \multicolumn{1}{c|}{x_{21}}                      & c_{21}                                           & \multicolumn{1}{c|}{x_{22}}                      & c_{22}                                           & \multicolumn{2}{c|}{}               & \multicolumn{1}{c|}{x_{2m}} & c_{2m} & \\\cline{2-9}
		\multirow{2}{*}{\(\vdots\)}    & \multicolumn{2}{c|}{\multirow{2}{*}{\(\vdots\)}} & \multicolumn{2}{c|}{\multirow{2}{*}{\(\vdots\)}} & \multicolumn{2}{c|}{\multirow{2}{*}{\(\ddots\)}} & \multicolumn{2}{c|}{\multirow{2}{*}{\(\vdots\)}} & \multirow{2}{*}{\(\vdots\)}                                                  \\
		                               & \multicolumn{2}{c|}{}                            & \multicolumn{2}{c|}{}                            & \multicolumn{2}{c|}{}                            & \multicolumn{2}{c|}{}                            &                                                                              \\\cline{2-9}
		\multirow{2}{*}{\(\lambda_n\)} & \multicolumn{2}{c|}{\lambda_n + \mu_1}           & \multicolumn{2}{c|}{\lambda_n + \mu_2}           & \multicolumn{2}{c|}{\multirow{2}{*}{\(\cdots\)}} & \multicolumn{2}{c|}{\lambda_n + \mu_m}           & \multirow{2}{*}{\(s_n\)}                                                     \\\cline{3-3}\cline{5-5}\cline{9-9}
		                               & \multicolumn{1}{c|}{x_{n1}}                      & c_{n1}                                           & \multicolumn{1}{c|}{x_{n2}}                      & c_{n2}                                           & \multicolumn{2}{c|}{}               & \multicolumn{1}{c|}{x_{nm}} & c_{nm} & \\\cline{2-9}
		\multicolumn{1}{c}{}           & \multicolumn{2}{c}{d_1}                          & \multicolumn{2}{c}{d_2}                          & \multicolumn{2}{c}{\cdots}                       & \multicolumn{2}{c}{d_m}                          & \multicolumn{1}{c}{}
	\end{array}
\]

Like with the simplex method, we must begin with a basic feasible solution to construct the initial tableau.
We can construct such a basic feasible solution by using the first supplier to satisfy the first consumer, then gradually using the next suppliers and consumers as we run out of supply or demand.
\( \bm \lambda \) and \( \bm \mu \) can be deduced by considering complementary slackness.
That is, if \( x_{ij} > 0 \) then \( \lambda_i + \mu_j = c_{ij} \).
For instance, consider this problem with three suppliers and four consumers.
The general transportation tableau would look like this:

\[
	\arraycolsep=2pt\def\arraystretch{1.2}
	\begin{array}{c|c|c|c|c|c|c|c|c|c}
		\multicolumn{1}{c}{}           & \multicolumn{2}{c}{\mu_1}              & \multicolumn{2}{c}{\mu_2}              & \multicolumn{2}{c}{\mu_3}              & \multicolumn{2}{c}{\mu_4}              & \multicolumn{1}{c}{}                                                          \\\cline{2-9}
		\multirow{2}{*}{\(\lambda_1\)} & \multicolumn{2}{c|}{\lambda_1 + \mu_1} & \multicolumn{2}{c|}{\lambda_1 + \mu_2} & \multicolumn{2}{c|}{\lambda_1 + \mu_3} & \multicolumn{2}{c|}{\lambda_1 + \mu_4} & \multirow{2}{*}{\(s_1\)}                                                      \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                               & \multicolumn{1}{c|}{x_{11}}            & c_{11}                                 & \multicolumn{1}{c|}{x_{12}}            & c_{12}                                 & \multicolumn{1}{c|}{x_{13}} & c_{13} & \multicolumn{1}{c|}{x_{14}} & c_{14} & \\\cline{2-9}
		\multirow{2}{*}{\(\lambda_2\)} & \multicolumn{2}{c|}{\lambda_2 + \mu_1} & \multicolumn{2}{c|}{\lambda_2 + \mu_2} & \multicolumn{2}{c|}{\lambda_2 + \mu_3} & \multicolumn{2}{c|}{\lambda_2 + \mu_4} & \multirow{2}{*}{\(s_2\)}                                                      \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                               & \multicolumn{1}{c|}{x_{21}}            & c_{21}                                 & \multicolumn{1}{c|}{x_{22}}            & c_{22}                                 & \multicolumn{1}{c|}{x_{23}} & c_{23} & \multicolumn{1}{c|}{x_{24}} & c_{24} & \\\cline{2-9}
		\multirow{2}{*}{\(\lambda_3\)} & \multicolumn{2}{c|}{\lambda_3 + \mu_1} & \multicolumn{2}{c|}{\lambda_3 + \mu_2} & \multicolumn{2}{c|}{\lambda_3 + \mu_3} & \multicolumn{2}{c|}{\lambda_3 + \mu_4} & \multirow{2}{*}{\(s_3\)}                                                      \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                               & \multicolumn{1}{c|}{x_{31}}            & c_{31}                                 & \multicolumn{1}{c|}{x_{32}}            & c_{32}                                 & \multicolumn{1}{c|}{x_{33}} & c_{33} & \multicolumn{1}{c|}{x_{34}} & c_{34} & \\\cline{2-9}
		\multicolumn{1}{c}{}           & \multicolumn{2}{c}{d_1}                & \multicolumn{2}{c}{d_2}                & \multicolumn{2}{c}{d_3}                & \multicolumn{2}{c}{d_4}                & \multicolumn{1}{c}{}
	\end{array}
\]
We will consider the problem given by
\[
	\vb s = \begin{pmatrix}
		14 \\ 10 \\ 9
	\end{pmatrix};\quad \vb d = \begin{pmatrix}
		12 \\ 5 \\ 8 \\ 8
	\end{pmatrix};\quad C = \begin{pmatrix}
		5 & 3 & 4 & 6 \\
		2 & 7 & 4 & 1 \\
		5 & 6 & 2 & 4
	\end{pmatrix}
\]
A basic feasible solution is given by
\[
	X = \begin{pmatrix}
		12 & 2 & 0 & 0 \\
		0  & 3 & 7 & 0 \\
		0  & 0 & 1 & 8
	\end{pmatrix}
\]
Complementary slackness gives
\begin{align*}
	\lambda_1 + \mu_1 & = 5 \\
	\lambda_1 + \mu_2 & = 3 \\
	\lambda_2 + \mu_2 & = 7 \\
	\lambda_2 + \mu_3 & = 4 \\
	\lambda_3 + \mu_3 & = 2 \\
	\lambda_3 + \mu_4 & = 4 \\
\end{align*}
This is a system of seven equations for six unknowns.
However, since we can always set \( \lambda_1 = 0 \), we can reduce this to a system of six equations for six unknowns.
\begin{align*}
	\mu_1             & = 5 \\
	\mu_2             & = 3 \\
	\lambda_2 + \mu_2 & = 7 \\
	\lambda_2 + \mu_3 & = 4 \\
	\lambda_3 + \mu_3 & = 2 \\
	\lambda_3 + \mu_4 & = 4 \\
\end{align*}
Hence,
\[
	\bm\lambda = \begin{pmatrix}
		0 \\ 4 \\ 2
	\end{pmatrix};\quad \bm\mu = \begin{pmatrix}
		5 \\3\\0\\2
	\end{pmatrix}
\]

\begin{theorem}
	When constructing a basic feasible solution in this way, the set of edges with strictly positive flow form a connected graph with no cycles.
	In particular, this graph is a \textit{spanning tree} \( T \) with exactly \( m + n - 1 \) edges.
	This allows us to always construct a system of equations as above.
\end{theorem}
No proof is given.
\[
	\arraycolsep=5pt\def\arraystretch{1.2}
	\begin{array}{c|c|c|c|c|c|c|c|c|c}
		\multicolumn{1}{c}{}   & \multicolumn{2}{c}{5}   & \multicolumn{2}{c}{3}  & \multicolumn{2}{c}{0}  & \multicolumn{2}{c}{2}  & \multicolumn{1}{c}{}                                       \\\cline{2-9}
		\multirow{2}{*}{\(0\)} & \multicolumn{2}{c|}{5}  & \multicolumn{2}{c|}{3} & \multicolumn{2}{c|}{0} & \multicolumn{2}{c|}{2} & \multirow{2}{*}{\(14\)}                                    \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                       & \multicolumn{1}{c|}{12} & 5                      & \multicolumn{1}{c|}{2} & 3                      & \multicolumn{1}{c|}{0}  & 4 & \multicolumn{1}{c|}{0} & 6 & \\\cline{2-9}
		\multirow{2}{*}{\(4\)} & \multicolumn{2}{c|}{9}  & \multicolumn{2}{c|}{7} & \multicolumn{2}{c|}{4} & \multicolumn{2}{c|}{6} & \multirow{2}{*}{\(10\)}                                    \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                       & \multicolumn{1}{c|}{0}  & 2                      & \multicolumn{1}{c|}{3} & 7                      & \multicolumn{1}{c|}{7}  & 4 & \multicolumn{1}{c|}{0} & 1 & \\\cline{2-9}
		\multirow{2}{*}{\(2\)} & \multicolumn{2}{c|}{7}  & \multicolumn{2}{c|}{5} & \multicolumn{2}{c|}{2} & \multicolumn{2}{c|}{4} & \multirow{2}{*}{\(9\)}                                     \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                       & \multicolumn{1}{c|}{0}  & 5                      & \multicolumn{1}{c|}{0} & 6                      & \multicolumn{1}{c|}{1}  & 2 & \multicolumn{1}{c|}{8} & 4 & \\\cline{2-9}
		\multicolumn{1}{c}{}   & \multicolumn{2}{c}{12}  & \multicolumn{2}{c}{5}  & \multicolumn{2}{c}{8}  & \multicolumn{2}{c}{8}  & \multicolumn{1}{c}{}
	\end{array}
\]

\subsection{Updating the transportation tableau}
First, we check if \( c_{ij} \geq \lambda_i + \mu_j \) for all \( i, j \).
If this is true, then our solution is optimal.
In our example \( c_{21} \geq \lambda_2 + \mu_1 \), so we are not at an optimal solution.
If \( (i,j) \notin T \) (where \( T \) is the spanning tree above, i.e.
\( x_{ij} = 0 \)) and \( c_{ij} < \lambda_i + \mu_j \), then \((i,j)\) and the edges of \( T \) form a loop.
We then increase \( x_{ij} \) as much as possible until another flow \(x_{i'j'}\) is forced to be zero.
Then we update the dual variables \( \bm \lambda, \bm \mu \) and repeat.

In our example, we will introduce a flow of \( x_{21} = \theta \).
This will change the amount of flow along some nonzero edges.
Doing this will force an update \( x_{11} \mapsto x_{11} - \theta \) due to constrained demand, \( x_{12} \mapsto x_{12} + \theta \) due to supply, and \( x_{22} \mapsto x_{22} - \theta \) due to demand.
We can then increase \( \theta \) to a maximum value of \( 3 \).
Now,
\[
	x = \begin{pmatrix}
		9 & 5 & 0 & 0 \\
		3 & 0 & 7 & 0 \\
		0 & 0 & 1 & 8
	\end{pmatrix}
\]
We now recalculate \( \bm\lambda,\bm\mu \) in the same way as above, which will give
\[
	\bm\lambda = \begin{pmatrix}
		0 \\-3\\-5
	\end{pmatrix};\quad \bm\mu = \begin{pmatrix}
		5 \\3\\7\\9
	\end{pmatrix}
\]
Reconstructing the tableau gives
\[
	\arraycolsep=5pt\def\arraystretch{1.2}
	\begin{array}{c|c|c|c|c|c|c|c|c|c}
		\multicolumn{1}{c}{}    & \multicolumn{2}{c}{5}  & \multicolumn{2}{c}{3}   & \multicolumn{2}{c}{7}  & \multicolumn{2}{c}{9}  & \multicolumn{1}{c}{}                                       \\\cline{2-9}
		\multirow{2}{*}{\(0\)}  & \multicolumn{2}{c|}{5} & \multicolumn{2}{c|}{3}  & \multicolumn{2}{c|}{7} & \multicolumn{2}{c|}{9} & \multirow{2}{*}{\(14\)}                                    \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                        & \multicolumn{1}{c|}{9} & 5                       & \multicolumn{1}{c|}{3} & 3                      & \multicolumn{1}{c|}{0}  & 4 & \multicolumn{1}{c|}{0} & 6 & \\\cline{2-9}
		\multirow{2}{*}{\(-3\)} & \multicolumn{2}{c|}{2} & \multicolumn{2}{c|}{0}  & \multicolumn{2}{c|}{4} & \multicolumn{2}{c|}{6} & \multirow{2}{*}{\(10\)}                                    \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                        & \multicolumn{1}{c|}{3} & 2                       & \multicolumn{1}{c|}{0} & 7                      & \multicolumn{1}{c|}{7}  & 4 & \multicolumn{1}{c|}{0} & 1 & \\\cline{2-9}
		\multirow{2}{*}{\(5\)}  & \multicolumn{2}{c|}{0} & \multicolumn{2}{c|}{-2} & \multicolumn{2}{c|}{2} & \multicolumn{2}{c|}{4} & \multirow{2}{*}{\(9\)}                                     \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                        & \multicolumn{1}{c|}{0} & 5                       & \multicolumn{1}{c|}{0} & 6                      & \multicolumn{1}{c|}{1}  & 2 & \multicolumn{1}{c|}{8} & 4 & \\\cline{2-9}
		\multicolumn{1}{c}{}    & \multicolumn{2}{c}{12} & \multicolumn{2}{c}{5}   & \multicolumn{2}{c}{8}  & \multicolumn{2}{c}{8}  & \multicolumn{1}{c}{}
	\end{array}
\]
Once again there is an edge where \( c_{ij} < \lambda_i + \mu_j \), notably \((i,j) = (2,4)\), with zero flow.
If \( x_{ij} = \theta \), then \( x_{23} \mapsto x_{23} - \theta \), \( x_{34} \mapsto x_{34} - \theta \), \( x_{33} \mapsto x_{33} + \theta \).
We can increase \( \theta \) only to \( 7 \).
Once again, updating the tableau gives

\[
	\arraycolsep=5pt\def\arraystretch{1.2}
	\begin{array}{c|c|c|c|c|c|c|c|c|c}
		\multicolumn{1}{c}{}    & \multicolumn{2}{c}{5}  & \multicolumn{2}{c}{3}  & \multicolumn{2}{c}{2}   & \multicolumn{2}{c}{4}  & \multicolumn{1}{c}{}                                       \\\cline{2-9}
		\multirow{2}{*}{\(0\)}  & \multicolumn{2}{c|}{5} & \multicolumn{2}{c|}{3} & \multicolumn{2}{c|}{2}  & \multicolumn{2}{c|}{4} & \multirow{2}{*}{\(14\)}                                    \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                        & \multicolumn{1}{c|}{9} & 5                      & \multicolumn{1}{c|}{5}  & 3                      & \multicolumn{1}{c|}{0}  & 4 & \multicolumn{1}{c|}{0} & 6 & \\\cline{2-9}
		\multirow{2}{*}{\(-3\)} & \multicolumn{2}{c|}{2} & \multicolumn{2}{c|}{0} & \multicolumn{2}{c|}{-1} & \multicolumn{2}{c|}{1} & \multirow{2}{*}{\(10\)}                                    \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                        & \multicolumn{1}{c|}{3} & 2                      & \multicolumn{1}{c|}{0}  & 7                      & \multicolumn{1}{c|}{0}  & 4 & \multicolumn{1}{c|}{7} & 1 & \\\cline{2-9}
		\multirow{2}{*}{\(0\)}  & \multicolumn{2}{c|}{5} & \multicolumn{2}{c|}{3} & \multicolumn{2}{c|}{2}  & \multicolumn{2}{c|}{4} & \multirow{2}{*}{\(9\)}                                     \\\cline{3-3}\cline{5-5}\cline{7-7}\cline{9-9}
		                        & \multicolumn{1}{c|}{0} & 5                      & \multicolumn{1}{c|}{0}  & 6                      & \multicolumn{1}{c|}{8}  & 2 & \multicolumn{1}{c|}{1} & 4 & \\\cline{2-9}
		\multicolumn{1}{c}{}    & \multicolumn{2}{c}{12} & \multicolumn{2}{c}{5}  & \multicolumn{2}{c}{8}   & \multicolumn{2}{c}{8}  & \multicolumn{1}{c}{}
	\end{array}
\]
In this current table, all optimality conditions are satisfied.
So the solution is
\[
	x = \begin{pmatrix}
		9 & 5 & 0 & 0 \\
		3 & 0 & 0 & 7 \\
		0 & 0 & 8 & 1
	\end{pmatrix}
\]
